package com.sean.sort;

import java.util.Arrays;

/**
 * 分配排序：桶排序，基数排序
 */
public class DistributionSort {
    /**
     * 桶排序： 支持负数，不稳定排序
     * @param array 待排序数组
     * @param min 数组中最小的数
     * @param max 数组中最大的数
     */
    public static void bucketSort(int[] array, int min, int max){
        long start = System.nanoTime();
        int[] bucket = new int[max - min + 1];    // 桶
        for(int i = 0; i < array.length; i++){
            bucket[array[i] - min] ++;
        }
        int j = 0;
        for(int i = 0; i < bucket.length; i++){
            while(bucket[i] > 0){
                array[j] = min + i;
                bucket[i] --;
                j++;
            }
        }
        long end = System.nanoTime();
        System.out.println("桶排序用时： " + (end - start) + "ns");
    }

    /**
     * 基数排序： 数组实现 LSD 稳定 不支持负数
     * @param array 待排序数组
     * @param digit 数组中数字的最大位数
     * @param radix 数组中数字的基数（进制）
     */
    public static void radixSort(int[] array, int digit, int radix){
        long start = System.nanoTime();
        int LSD = 1;                        // 取个位
        for(int i = 0; i < digit; i ++){
            int[] bucket = new int[radix];      // 桶，十进制就是 0 - 9
            // 统计 LSD 位相同的数字的个数
            for(int j = 0; j < array.length; j++){
                bucket[(array[j] / LSD) % radix] ++;
            }
            // 计算元素在数组中正确的位置
            for(int j = 1; j < radix; j++){
                bucket[j] += bucket[j - 1];
            }
            // count[i] 中记录的是元素 i + 1 的排序后开始位置
            // array[count[i] - 1] 开始往前追溯
            int[] temp = new int[array.length];
            for(int j = array.length - 1; j >= 0; j--){
                int k = (array[j] / LSD) % radix;
                temp[bucket[k] - 1] = array[j];
                bucket[k] --;
            }
            System.arraycopy(temp, 0, array, 0, temp.length);
            LSD *= radix;               // 取高一位
        }
        long end = System.nanoTime();
        System.out.println("基数排序用时： " + (end - start) + "ns");
    }

    public static void main(String[] args) {
        final int _10w = 100000;
        // 桶排序用时： 5850100ns
        int [] test1 = new int[_10w];
        for(int i = _10w, j = 0; i > 0; i--, j++){
            test1[j] = i % 100;
        }
        DistributionSort.bucketSort(test1, 0, 99);

        // 基数排序用时： 22644100ns
        int [] test2 = new int[_10w];
        for(int i = _10w, j = 0; i > 0; i--, j++){
            test2[j] = i % 50000;
        }
        DistributionSort.radixSort(test2, 5, 10);
    }
}
